/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._113;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 *
 * 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
 *
 * 说明: 叶子节点是指没有子节点的节点。
 *
 * 示例:
 * 给定如下二叉树，以及目标和 sum = 22，
 *
 *               5
 *              / \
 *             4   8
 *            /   / \
 *           11  13  4
 *          /  \    / \
 *         7    2  5   1
 * 返回:
 *
 * [
 *    [5,4,11,2],
 *    [5,8,4,5]
 * ]
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._113
 * @ClassName: PathSumII
 * @Author: linyaonan
 * @Date: 2020/1/7 13:42
 */
public class PathSumII {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {
            return result;
        }
        List<Integer> add = new ArrayList<>();
        bfs(root, sum, 0, add);
        return result;
    }

    private void bfs(TreeNode node, int sum, Integer count, List<Integer> add) {
        if (node.left == null && node.right == null) {
            count += node.val;
            add.add(node.val);
            if (count == sum) {
                List<Integer> save = new ArrayList<>(add.size());
                save.addAll(add);
                result.add(save);
            }
        } else {
            count += node.val;
            add.add(node.val);
            if (node.left != null) {
                bfs(node.left, sum, count, add);
                add.remove(add.size() - 1);
            }

            if (node.right != null) {
                bfs(node.right, sum, count, add);
                add.remove(add.size() - 1);
            }
        }
    }
}
